package com.njupt.DynamicProgramming;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/20 8:55
 * @Description: 509. 斐波那契数
 * @Version: 1.0
 */


public class Fib_509 {

    /**
     * 动态规划,结果保存在dp数组种
     * @param n
     * @return
     */
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;

        for (int i = 2; i <=n ; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    /**
     * 动态规划，结果迭代保留
     * @param n
     * @return
     */
    public int fib1(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        int pre = 0;
        int rear = 1;
        int cur = -1;
        for (int i = 2; i <=n ; i++) {
            cur = pre + rear;
            pre = rear;
            rear = cur;
        }
        return cur;
    }

    /**
     * 动态规划，递归法
     * @param n
     * @return
     */
    public int fib2(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        int num = fib2(n-1) + fib2(n-2);
        return num;
    }

    public static void main(String[] args) {
        Fib_509 test = new Fib_509();
        System.out.println(test.fib2(4));
    }
}
